Recursion

ENDURING UNDERSTANDING

LEARNING OBJECTIVE

Determine the result of executing recursive methods.

ESSENTIAL KNOWLEDGE

A recursive method is a method that calls itself.
Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
Each recursive call has its own set of local variables, including the formal parameters.
Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
Any recursive solution can be replicated through the use of an iterative approach.
Recursion can be used to traverse String, array, and ArrayList objects.

Recursive Searching and Sorting

ENDURING UNDERSTANDING

LEARNING OBJECTIVE

Apply recursive search algorithms to information in String, 1D array, or ArrayList objects.

ESSENTIAL KNOWLEDGE

Data must be in sorted order to use the binary search algorithm.
The binary search algorithm starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each iteration until the desired value is found or all elements have been eliminated.
Binary search can be more efficient than sequential/linear search.
The binary search algorithm can be written either iteratively or recursively.

ENDURING UNDERSTANDING

LEARNING OBJECTIVE

Apply recursive algorithms to sort elements of array or ArrayList objects.

ESSENTIAL KNOWLEDGE

Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.